import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;


public class Leetcode436 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findRightInterval(new int[][]{{4, 5}, {2, 3}, {1, 2}})));
    }

    public static int[] findRightInterval(int[][] intervals) {
        HashMap<Integer, HashMap<Integer, Integer>> indexMap = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            HashMap<Integer, Integer> map = indexMap.getOrDefault(intervals[i][0], new HashMap<>());
            map.put(intervals[i][1], i);
            indexMap.put(intervals[i][0], map);
        }

        int[][] origin = intervals.clone();

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        int[] res = new int[intervals.length];
        for (int i = 0; i < origin.length; i++) {
            int right = origin[i][1];
            int index = Arrays.binarySearch(intervals, 0, intervals.length, new int[]{right, 0}, Comparator.comparingInt(a -> a[0]));
            if (index < 0) {
                index = -index - 1;
            }

            if (index < intervals.length) {
                res[i] = indexMap.get(intervals[index][0]).get(intervals[index][1]);
                continue;
            }

            res[i] = -1;
        }

        return res;
    }
}

